/*
https://leetcode.cn/problems/delivering-boxes-from-storage-to-ports/solutions/2005717/cong-cang-ku-dao-ma-tou-yun-shu-xiang-zi-4uya/
 */
import java.util.Deque;
import java.util.LinkedList;

public class Solution1687 {
    public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
        long[] w=new long[boxes.length+1];
        int[] neg=new int[boxes.length+1];
        for (int i=1;i<w.length;i++){
            w[i]=w[i-1]+boxes[i-1][1];
            if (i>1){
                neg[i]=neg[i-1]+(boxes[i-2][0]==boxes[i-1][0]?0:1);
            }
        }
        int[] f=new int[boxes.length+1];
        int[] g=new int[boxes.length+1];
        Deque<Integer> deque=new LinkedList<>();
        deque.offer(0);
        for (int i=1;i<f.length;i++){
            while (i-deque.peekFirst()>maxBoxes || w[i]-w[deque.peekFirst()]>maxWeight){
                deque.pollFirst();
            }
            f[i]=g[deque.peekFirst()]+neg[i]+2;
            if (i!=boxes.length){
                g[i]=f[i]-neg[i+1];
                while (!deque.isEmpty() && g[i]<=g[deque.peekLast()]){
                    deque.pollLast();
                }
                deque.offerLast(i);
            }
        }
        return f[f.length-1];
    }

    public static void main(String[] args) {
        System.out.println(new Solution1687().boxDelivering(new int[][]{{1,1},{2,1},{1,1}},2,3,3));
    }
}
